import math
from collections import Counter

def euclidean_distance(x1, x2):
    """计算两个样本之间的欧氏距离"""
    return math.sqrt(sum([(a - b) **2 for a, b in zip(x1, x2)]))

def knn_predict(train_data, train_labels, x, k):
    """
    单个样本的k近邻预测
    train_data: 训练样本列表（每个样本为可迭代对象）
    train_labels: 训练样本对应的标签列表
    x: 待预测样本
    k: 近邻数量
    return: 预测标签
    """
    # 计算待预测样本与所有训练样本的距离
    distances = []
    for i, sample in enumerate(train_data):
        dist = euclidean_distance(sample, x)
        distances.append((dist, train_labels[i]))  # (距离, 标签)
    
    # 按距离排序，取前k个最近邻
    distances.sort()  # 按距离升序排列
    k_nearest = distances[:k]
    
    # 提取近邻的标签并投票（多数表决）
    k_labels = [label for (dist, label) in k_nearest]
    most_common = Counter(k_labels).most_common(1)  # 取出现次数最多的标签
    return most_common[0][0]

def knn_classify(train_data, train_labels, test_data, k=3):
    """
    k近邻分类器
    train_data: 训练样本列表
    train_labels: 训练样本标签列表
    test_data: 测试样本列表（待预测）
    k: 近邻数量
    return: 测试样本的预测标签列表
    """
    # 输入校验
    if len(train_data) != len(train_labels):
        raise ValueError("训练样本与标签数量不匹配")
    if k <= 0 or k > len(train_data):
        raise ValueError("k值必须为正整数且不大于训练样本数量")
    
    # 对每个测试样本进行预测
    predictions = []
    for x in test_data:
        pred = knn_predict(train_data, train_labels, x, k)
        predictions.append(pred)
    return predictions